//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：n = 4
//输出：2
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。 
// 
// 
// 
// Related Topics 回溯 👍 314 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：N皇后 II
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P52_NQueensIi {
    public static void main(String[] args) {
        Solution solution = new P52_NQueensIi().new Solution();
        for (int i = 1; i <= 12; i++) {
            MyUtil.printf("{}皇后摆法：{}", i, solution.totalNQueens(i));
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int totalNQueens(int n) {
            if (n <= 0) {
                return 0;
            }
            return process(0, new int[n]);
        }

        /**
         * 当前来到第i行，i-1及以上的决定放在record数组中，返回能放下的方法数
         * record[x]=y表示第x行的皇后放在了y列上
         */
        private int process(int i, int[] record) {
            // 总列数
            int N = record.length;
            // 能来到最后表示前面的都有效
            if (i == N) {
                return 1;
            }
            // 枚举皇后在每列的情况
            int ways = 0;
            for (int j = 0; j < N; j++) {
                if (valid(record, i, j)) {
                    record[i] = j;
                    ways += process(i + 1, record);
                }
            }
            return ways;
        }

        /**
         * 判断 [i,j]位置的皇后是否合理
         */
        private boolean valid(int[] record, int i, int j) {
            for (int k = 0; k < i; k++) {
                // 共列
                if (j == record[k]) {
                    return false;
                }
                // 共斜线
                if (Math.abs(i - k) == Math.abs(j - record[k])) {
                    return false;
                }
            }
            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}